﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Diagnostics.Contracts;

namespace ReactiveCode.Expressions
{
    partial class ReactiveExpression
    {
        class OrderComparerImpl : IComparer<ReactiveExpression>
        {
            int IComparer<ReactiveExpression>.Compare(ReactiveExpression x, ReactiveExpression y)
            {
                return CompareOrder(x, y) ?? 0;
            }
        }
        readonly static IComparer<ReactiveExpression> _orderComparer = new OrderComparerImpl();
        internal static IComparer<ReactiveExpression> OrderComparer
        {
            get { return _orderComparer; }
        }
        internal static int? CompareOrder(ReactiveExpression x, ReactiveExpression y)
        {
            if (x == y)
                return 0;
            else if (x == null)
                return -1;
            else if (y == null)
                return 1;

            if (x.Parent != y.Parent)
            {
                if (x.Parent == null && y.Parent == null)
                    return null; // common ancestor not found
                else if (y.Parent == x)
                    return -1;

                var xAncestors = x.MeAndAncestors().ToList();

                if (xAncestors.Contains(y))
                    return 1; // y is ancestor of x

                for (; ; )
                {
                    int pos = xAncestors.IndexOf(y.Parent);
                    if (pos == 0)
                        return -1; // x is ancestor of y
                    else if (pos > 0)
                    {
                        // common ancestor is found
                        x = xAncestors[pos - 1];
                        break;
                    }

                    y = y.Parent;
                    if (y == null)
                        return null; // common ancestor not found
                }
            }

            Contract.Assert(x.Parent == y.Parent);
            var parent = (IExpressionParent)x.Parent;
            if (parent == null)
            {
                var xRoot = (IRootExpression)x.Root;
                var yRoot = (IRootExpression)y.Root;
                if (xRoot == null || yRoot == null)
                    return null;
                Contract.Assert(xRoot != yRoot);
                if (xRoot.Host == yRoot.Host)
                    return xRoot.ActivationTime.CompareTo(yRoot.ActivationTime);
                else
                    return xRoot.Host.CreationTime.CompareTo(yRoot.Host.CreationTime);
            }

            int xIdx = parent.Children.IndexOf(x);
            int yIdx = parent.Children.IndexOf(y);
            Contract.Assert(xIdx >= 0 && yIdx >= 0);
            return xIdx.CompareTo(yIdx);
        }
    }
}